package cn.cxq.learning.dynamic_programming;

/**
 * 牛客题霸-研发最爱考
 * 求路径
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：28845
 * 本题知识点： 动态规划
 *  算法知识视频讲解
 * 题目描述
 * 一个机器人在m×n大小的地图的左上角（起点）。
 * 机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
 * 可以有多少种不同的路径从起点走到终点？
 *
 * 备注：m和n小于等于100,并保证计算结果在int范围内
 *
 * 示例1
 * 输入
 * 复制
 * 2,1
 * 返回值
 * 复制
 * 1
 * 示例2
 * 输入
 * 复制
 * 2,2
 * 返回值
 * 复制
 * 2
 *  关联企业
 * 字节跳动网易互娱新浪
 *  关联职位
 * 前端研发算法
 */
public class UniquePaths {

    // 简单动态规划解题
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) {
                    dp[i][j] += dp[i - 1][j];
                }
                if (j > 0){
                    dp[i][j] += dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}
